class Solution {
public:
/*  
//暴力遍历  
    int search(vector<int>& nums, int target) {
        int cnt = 0;
        for(auto i : nums){
            if(i == target){
                cnt++;
            }
        }

        return cnt;
    }
*/
//优化二分查找
    //找到第一个 target 元素的下标
    int FirstNum(vector<int>& nums, int start, int end, int k){
        if(start > end){
            return -1;
        }

        int mid = (start + end) / 2;
        if(nums[mid] == k){
            if(mid > 0 && nums[mid - 1] != k
            || mid == 0){
                // nums[mid]正好是第一个k（前一个元素不等于k）
                return mid;  //返回第一个k的下标
            }
            else {
                end = mid - 1;
            }
        }
        else if(nums[mid] > k){
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
        return FirstNum(nums, start, end, k);
    }

    //找到最后一个 target 元素的下标
    int LastNum(vector<int>& nums, int start, int end, int k){
        if(start > end){
            return -1;
        }

        int mid = (start + end) / 2;
        if(nums[mid] == k){
            if(mid < nums.size() - 1 && nums[mid + 1] != k
            || mid == nums.size() - 1){
                // nums[mid]正好是最后一个k（后一个元素不等于k）
                return mid;
            }
            else {
                start = mid + 1;
            }
        }
        else if(nums[mid] > k){
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
        return LastNum(nums, start, end, k);
    }
    
    int search(vector<int>& nums, int target) {
        if(nums.size() == 0){
            return 0;
        }

        int first = FirstNum(nums, 0, nums.size() - 1, target);
        int last = LastNum(nums, 0, nums.size() - 1, target);

        if(first >= 0 && last >= 0){  
            return last - first + 1;
        }
        return 0;
    }
};